/**
 * 
 */
package tree.passed2;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class PathSumII {

	/**
	Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
	For example:
	Given the below binary tree and sum = 22,

	          5
	         / \
	        4   8
	       /   / \
	      11  13  4
	     /  \    / \
	    7    2  5   1

	return

	[
	[5,4,11,2],
	[5,8,4,5]
	]
	 */
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> solutions = new ArrayList<>();
		pathSumHelper(root, sum, new ArrayList<Integer>(), solutions);
		return solutions;
	}

	public void pathSumHelper(TreeNode root, int sum, List<Integer> solution,
	        List<List<Integer>> solutions) {
	    if (root == null)
	        return;
	    
	    sum -= root.val;
	    solution.add(root.val);
	    if (root.left == null && root.right == null && sum == 0) {
	        solutions.add(new ArrayList<>(solution));   
	    }
	    else {
	        pathSumHelper(root.left, sum, solution, solutions);
	        pathSumHelper(root.right, sum, solution, solutions);
	    }
	    
	    solution.remove(solution.size() - 1);
	}	
	
	public void pathSumHelp(TreeNode root, int sum, ArrayList<Integer> buffer,
	        ArrayList<ArrayList<Integer>> result) {
		if (root == null)
			return;

		buffer.add(root.val);
		if (root.val == sum && root.left == null && root.right == null) {
			result.add(new ArrayList<Integer>(buffer));
			buffer.remove(buffer.size() - 1);
			return;
		}

		pathSumHelp(root.left, sum - root.val, buffer, result);
		pathSumHelp(root.right, sum - root.val, buffer, result);

		buffer.remove(buffer.size() - 1);
	}
	
//    public List<List<Integer>> pathSum(TreeNode root, int sum) {
//        List<List<Integer>> solutions = new ArrayList<>();
//        if (root == null)
//            return solutions;
//        pathSumHelper(root, new ArrayList<Integer>(), solutions, sum);
//        return solutions;
//    }
//    
//    private void pathSumHelper(TreeNode root, List<Integer> accuList, List<List<Integer>> solutions, int sum) {
//        sum -= root.val;
//        accuList.add(root.val);
//        if (root.left == null && root.right == null) {
//            if (sum == 0 && !accuList.isEmpty())
//                solutions.add(accuList);
//        }
//        else {
//            if (root.left != null) {
//                pathSumHelper(root.left, new ArrayList<>(accuList), solutions, sum); 
//            }
//            if (root.right != null) {
//                pathSumHelper(root.right, new ArrayList<>(accuList), solutions, sum);  
//            }
//        }
//    }

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public PathSumII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
